package com.list;

/**
 * 顺序链表:
 * 能够使得再插入时就满足从小到大的有序状态
 */
public class OrderedList implements ILinkedList {
    private int count;//节点个数
    LinkedNode root;

    public int getCount() {
        return count;
    }

    /*插入节点*/
    @Override
    public void insert(int key) {
        if (root.next == null) {
            root.next = new LinkedNode(key);
        } else {
            LinkedNode p = root;
            while (true) {
                if (p.next == null) {
                    p.next = new LinkedNode(key);
                    break;
                } else if (p.next.key < key) {
                    p = p.next;
                } else {
                    LinkedNode node = new LinkedNode(key);
                    node.next = p.next;
                    p.next = node;
                    break;
                }
            }

        }
        count++;
    }

    @Override
    public int delete() {
        LinkedNode p = root;
        assert !isEmpty();
        while (p.next.next != null) {
            p = p.next;
        }
        int key = p.next.key;
        p.next = null;
        return key;
    }

    public int popFirst() {
        LinkedNode p = root;
        assert !isEmpty();
        int key = p.next.key;
        if (p.next.next != null) {
            p.next = p.next.next;
        } else {
            p.next = null;
        }
        return key;
    }

    @Override
    public boolean isEmpty() {
        return root.next == null;
    }

    //将会从小到大的输出
    public int[] removeAll() {
        int[] arr = new int[count];
        int i = 0;
        while (!isEmpty()) {
            arr[i] = root.next.key;
            i++;
            root.next = root.next.next;
        }
        count = 0;
        return arr;
    }

    public OrderedList() {
        root = new LinkedNode(1);
        count = 0;
    }
}
